package dp;

public class MaximumSubarray53 {

    public int maxSubArray(int[] nums) {
        // 以i为尾的最大的和, 包含i
        int[] subSum = new int[nums.length];
        int maxSubSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            // 先算入自己
            subSum[i] = nums[i];
            if (i > 0 && subSum[i-1] > 0) {
                // 如果全面的大于0, 加上
                subSum[i] += subSum[i-1];
            }
            // 可能要更新当前最大值
            if (subSum[i] > maxSubSum) {
                maxSubSum = subSum[i];
            }
        }
        return maxSubSum;
    }
}
